Méthode de type off-policy avec approximations¶
6. Méthode par descente du gradient sur l'erreur de Bellman¶
6.1. Intérêt de la méthode SGD¶
Notre objectif est de mettre en place la méthode par descente stochastique du gradient, dans laquelle les mises à jour sont réalisées en utilisant le gradient négatif de la fonction d'objectif. Ces méthodes sont considérées comme stables et possèdent de très bonnes propriétés de convergence. Sur l'ensemble des algorithmes que nous avons étudiés, seules les méthodes de Monte-Carlo sont de vraies méthodes SGD. Elles convergent de manière robuste lors d'un apprentissage on-policy ou off-policy, ainsi qu'avec l'utilisation de fonctions d'approximations non-linéaires, mais sont souvent plus lentes que les méthodes de semi-gradient (qui "boostrap"). Ces dernières peuvent diverger lors d'un apprentissage off-policy et lorsque les approximations de fonctions sont non-linéaires. Avec une vrai méthode SGD, ces divergences ne devraient pas arriver.
Le point d'orgue de la méthode SGD est le choix d'une fonction d'objectif à optimiser. Nous allons voir dans ce qui suit les origines et les limites de la fonction d'objectif la plus populaire, celle basée sur l'erreur de Bellman que nous avons introduite précédemment. Bien que cette approche a été très populaire, nous allons voir qu'elle ne permet pas de mettre en place des algorithmes d'apprentissages optimaux.
6.2. Première approche : optimisation basée sur de l'erreur TD¶
Algorithme naïf du gradient résiduel
Laissons pour le moment de côté l'erreur de Bellman et intéressons-nous à optimiser une quantité plus simple, comme l'espérance de la valeur quadratique de l'erreur TD. Dans sa forme générale, l'estimation de l'erreur TD(0) avec prise en compte du facteur de remise est la suivante :
La fonction d'objectif pourrait être alors la valeur quadratique moyenne de l'erreur TD :
$\overline {TDE} \left( \textbf{w} \right) = \sum\limits_{s \in S} {\mu \left( s \right)} E\left[ {{\delta _t}^2|{S_t} = s,{A_t} \sim \pi } \right]$
$\quad \quad \quad \quad = \sum\limits_{s \in S} {\mu \left( s \right)} E\left[ {{\rho _t}{\delta _t}^2|{S_t} = s,{A_t} \sim b} \right]$
$ \quad \quad \quad \quad = E_b\left[ {{\rho _t}{\delta _t}^2} \right]{\rm{(si }} \: \mu \: {\rm{ \: est \: la \: distribution \: rencontrée \: en \: suivant \: la \: stratégie \: }}b{\rm{)}}$
La dernière équation est adaptée à l'utilisation de l'algorithme SGD car la valeur de l'objectif peut être calculée par échantillonnage des résultats obtenus à partir des expériences en suivant la stratégie comportementale $b$. On peut donc en déduire l'algorithme des mises à jour SGD :
${\textbf{w}_{t + 1}} = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \left( {{E_b}\left[ {{\rho _t}{\delta _t}^2} \right]} \right)$
$ \quad \quad \: = {\textbf{w}_t} - \frac{1}{2}\alpha {E_b}\left[ {\nabla \left( {{\rho _t}{\delta _t}^2} \right)} \right]$
$ \quad \quad \: = {\textbf{w}_t} - \alpha {\rho _t}{\delta _t}{E_b}\left[ {\nabla \left( {{\delta _t}} \right)} \right]$
$ \quad \quad \: = {\textbf{w}_t} - \alpha {\rho _t}{\delta _t}\nabla \left[ {{R_{t + 1}} + \gamma \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right) - \hat v\left( {{S_t},{\textbf{w}_t}} \right)} \right]$
$ \quad \quad \: = {\textbf{w}_t} + \alpha {\rho _t}{\delta _t}\left[ {\nabla \hat v\left( {{S_t},{\textbf{w}_t}} \right) - \gamma \nabla \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right)} \right]$
On reconnait ici l'expression de l'algorithme semi-gradient TD déjà rencontré dans l'introduction aux méthodes semi-gradient :
... avec un terme supplémentaire qui complète notre algorithme, faisant de cet algorithme un vrai algorithme SGD possédant une très bonne qualité de convergence. Nous appellerons cet algorithme l'algorithme naïf du gradient résiduel.
Exemple de mauvaise convergence
Bien que possédant de très bonnes qualité de convergence, cet algorithme ne converge pas forcément au bon endroit comme le montre l'exemple ci-dessous.
L'épisode commence sur l'état A et se sépare de manière aléatoire, une fois sur deux, en allant sur l'état B (et ensuite de manière déterministe sur l'état final avec une récompense de 1) ou alors sur l'état C (et ensuite de manière déterministe sur l'état terminal avec une récompense nulle). Les récompenses obtenues en sortie de l'état A sont toujours nulles. Comme il s'agir d'un problème épisodique, nous prenons un facteur de remise $\gamma=1$. On assume que l'entrainement se fait en ligne (on-policy) et donc notre ratio d'échantillonnage préférentiel est donc toujours $\rho_t=1$. Enfin, on assume utiliser des fonctions de valeurs des états tabulaires, ce qui fait que les valeurs données aux états sont indépendantes les unes des autres.
Depuis l'état A, le revenu vaut donc 1 la moitié du temps et 0 l'autre moitié du temps. La valeur de l'état A doit donc être $V_A=0.5$. On doit également avoir $V_B=1$ et $V_C=0$. Toutes les méthodes tabulaires vues dans la formation à l'initiation à l'apprentissage par renforcement convergent correctement vers ces valeurs.
Cependant, l'algorithme naïf du gradient résiduel converge vers d'autres valeurs pour les états B et C. Il converge vers $V_B=3/4$ et $V_C=1/4$ ($V_A$ converge correctement vers 0.5). Avec ces valeurs, les erreurs $\overline {TDE}$ lors des transitions sont les suivantes :
- La première transition pour chaque épisode passe soit de A vers B, avec un changement de $V_B-V_A=1/4$ ou de A vers C, avec un changement de $V_C-V_A=-1/4$. Puisque la récompense est nulle sur ces transitions et que $\gamma=1$, ces changements correspondent aux erreurs TD, et donc l'espérance de la valeur quadratique de l'erreur TD est toujours égale à $\frac{1}{2}{\left( {\frac{1}{4}} \right)^2} + \frac{1}{2}{\left( {\frac{{ - 1}}{4}} \right)^2} = \frac{1}{{16}}$ sur la première transition.
- De manière similaire, la seconde transition passe soit de B vers l'état final avec une erreur TD de $(1-3/4)=1/4$ ou bien de C vers l'état final avec une erreur TD de $(0-1/4)=-1/4$. L'espérance de la valeur quadratique de l'erreur est donc encore une fois de $1/16$.
- La moyenne de l'erreur quadratique est donc ici de $\frac{1}{2}\left( {\frac{1}{{16}} + \frac{1}{{16}}} \right) = \frac{1}{{16}}$.
Dans le cas des valeurs vraies ($V_A=0.5$, $V_B=1$ et $V_C=0$) les erreurs $\overline {TDE}$ sur les transitions sont les suivantes :
- La première transition apporte un changement de $0.5$ en passant sur l'état B ou bien un changement de $-0.5$ en passant sur l'état C. L'espérance de la valeur quadratique de l'erreur TD est donc de $\frac{1}{2}{\left( {\frac{1}{2}} \right)^2} + \frac{1}{2}{\left( {\frac{{ - 1}}{2}} \right)^2} = \frac{1}{4}$.
- La seconde transition passe soit de B vers l'état terminal avec une erreur TD de $(1-1)=0$ ou de C vers l'état final avec une erreur TD de $(0-0)=0$. L'espérance de l'erreur quadratique est donc nulle.
- La moyenne de l'erreur quadratique est donc ici de $\frac{1}{2}\left( {\frac{1}{4} + 0} \right) = \frac{1}{8}$
On voit donc que les résultats donnés par l'algorithme naïf du gradient résiduel minimisent davantage la fonction d'objectif $\overline {TDE}$ mais ne donnent pas les vraies valeurs. En conclusion, minimiser l'espérance de la valeur quadratique de l'erreur TD ne permet pas d'obtenir les vraies valeurs des états.
6.3. Seconde approche : optimisation basée sur de l'erreur de Bellman¶
Rappels sur l'erreur de Bellman
On a vu en étudiant l'aspect géométrique des fonctions des valeurs que l'erreur de Bellman correspond à l'espérance de l'erreur TD:
$ \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = {E}\left[ {{R_{t + 1}} + \gamma {v_\textbf{w}}\left( {{S_{t + 1}}} \right) - {v_\textbf{w}}\left( {{S_t}} \right)|{S_t} = s,{A_t} \sim \pi } \right]$
Nous avons également vu que la valeur quadratique moyenne de l'erreur de Bellman s'exprime à partir de la norme du vecteur erreur de Bellman, qui représente le vecteur construit à partir de l'ensemble des erreurs de Bellman issues des états de l'environnement :
Si les vraies valeurs sont apprises, l'erreur de Bellman est nulle sur chaque état. Cependant, on ne peut pas obtenir une erreur nulle car les la vraie fonction des valeurs des états n'est pas dans le sous-espace vectoriel qui contient l'approximation de la fonction :
Algorithme du gradient résiduel
Regardons quand même ce que nous obtenons comme relations en cherchant à minimiser la valeur quadratique moyenne de l'erreur de Bellman $\overline {BE}$ :
${\textbf{w}_{t + 1}} = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \left( {\left\| {E\left[ {{\delta _t}|{S_t} = s,{A_t} = \pi } \right]} \right\|_\mu ^2} \right)$
$ \quad \quad \: = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \left( {\sum\limits_{s \in S} {\mu \left( s \right)E{{\left[ {{\delta _t}|{S_t} = s,{A_t} = \pi } \right]}^2}} } \right)$
$\quad \quad \: = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \left( {\sum\limits_{s \in S} {\mu \left( s \right)E{{\left[ {{\rho _t}{\delta _t}|{S_t} = s,{A_t} = b} \right]}^2}} } \right)$
$\quad \quad \: = {\textbf{w}_t} - \frac{1}{2}\alpha \nabla \left( {{E_b}{{\left[ {{\rho _t}{\delta _t}} \right]}^2}} \right)$
$ \quad \quad \: = {\textbf{w}_t} - \alpha {E_b}\left[ {{\rho _t}{\delta _t}} \right]\nabla \left[ {{E_b}\left[ {{\rho _t}{\delta _t}} \right]} \right]$
$\quad \quad \: = {\textbf{w}_t} - \alpha {E_b}\left[ {{\rho _t}{\delta _t}} \right]{E_b}\left[ {\nabla \left[ {{\rho _t}{\delta _t}} \right]} \right]$
Si on prend en compte uniquement les échantillons et non les espérance, et en faisant abstraction du ratio d'échantillonnage préférentiel, on retombe sur notre premier algorithme. Mais il est naïf car les équations dont intervenir les états $S_{t+1}$ :
$\quad \quad \: = {\textbf{w}_t} + \alpha {E_b}\left[ {{\rho _t}\left( {{R_{t + 1}} + \gamma \hat v\left( {{S_{t + 1}},\textbf{w}} \right) - \hat v\left( {{S_t},\textbf{w}} \right)} \right)} \right]{E_b}\left[ {{\rho _t}\left( {\nabla \hat v\left( {{S_t},{\textbf{w}_t}} \right) - \gamma \nabla \hat v\left( {{S_{t + 1}},{\textbf{w}_t}} \right)} \right)} \right]$
Cet algorithme est appelé l'algorithme résiduel du gradient. On remarque qu'il fait appel à un produit de deux espérances intervenant chacune sur l'état suivant $S_{t+1}$.
Afin d'obtenir une valeur non baisée du produit des espérances, il faudrait obtenir deux valeurs indépendantes sur l'état suivant, ce qui n'est pas possible lorsque l'agent est en interaction dans son environnement. Une seule des deux espérances peut être échantillonnée mais pas les deux en même temps.
Il y a deux possibilités pour que cet algorithme puisse être utilisé:
- Dans le cas des environnements déterministes, les deux échantillons seront forcément les mêmes. Dans ce cas, l'algorithme est équivalent à l'algorithme naïf vu précédemment.
- Si l'environnement est simulé, alors on peut obtenir les deux échantillons de manière indépendante.
Dans ces deux cas, l'algorithme résiduel du gradient converge vers un minimum. De plus, comme c'est un vrai algorithme SGD, la convergence est robuste avec les approximations linéaires. Dans le cas des approximations linéaires, la convergence est toujours vers un unique poids $\textbf{w}$ qui minimise l'erreur de Bellman $\overline {BE}$.
Il existe cependant trois raisons pour lesquelles cet algorithme n'est pas satisfaisant :
- Il est beaucoup plus lent que les méthodes semi-gradient.
- Il peut converger vers des valeurs fausses dans le cas d'utilisation d'approximations de fonctions.
- L'erreur de Bellman ne peut pas être apprise à partir de l'observation d'évènements, même s'ils sont infinis. L'utilisation de l'erreur de Bellman comme objectif n'est réalisable que dans des environnements dont le MDP est complètement connu.
Exemple de mauvaise convergence
Prenons l'exemple de l'environnement à 3 états où les épisodes commencent soit sur l'état A1 ou A2, avec des probabilités égales. Ces deux états, vus par la fonction d'approximation, sont vus exactement de la même manière, comme un seul état A, dont les caractéristiques sont distinctes et non corrélées des autres états B et C. Ces deux derniers états sont également indépendants l'un de l'autre. Plus précisément, les paramètres de l'approximateur sont au nombre de trois : un pour la valeur de l'état B, un pour la valeur de l'état C et un pour les valeurs des états A1 et A2. En dehors du fait que la sélection de l'état initiale soit aléatoire, le système est déterministe. Si l'agent commence sur l'état A1, alors la transition se fera vers l'état B avec une récompense de 0 et se terminera ensuite sur l'état terminal avec une récompense de 1. Si l'agent débute sur l'état A2, alors la transition se fera sur l'état C et se terminera ensuite sur l'état terminal avec une récompense nulle.
Du point de vue de l'algorithme d'apprentissage qui ne perçoit que les caractéristiques du système, celui-ci est identique à celui déjà étudié précédemment. Les vraies valeurs des états sont $V_{A1}=V_{A2}=0.5$, $V_B=1$ et $V_C=0$.
Les valeurs que va trouver l'algorithme semi-gradient TD vont être les vraies valeurs, alors que l'algorithme naïf résiduel du gradient va converger vers les valeurs $V_B=3/4$, $V_C=1/4$.
Toutes les transitions sont déterministes donc l'algorithme résiduel du gradient va converger vers les mêmes valeurs que celles trouvées par l'algorithme naïf ! Par conséquent, la solution trouvé en minimisant l'erreur utilisée par l'algorithme naïf est la même que celle trouvée en minimisant l'erreur utilisé par l'algorithme non naïf. On peut en conclure que les deux erreurs $\overline {BE}$ (erreur de Bellman) et $\overline {TDE}$ (valeur quadratique moyenne de l'erreur TD) sont les mêmes lorsque l'environnement est déterministe.